/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/palindromic-substrings
   @Language: C++
   @Datetime: 19-04-27 16:31
   */

// Method 1, Time O(n^2*k), Space O(1), Time 50ms
class Solution {
public:
	/**
	 * @param str: s string
	 * @return: return an integer, denote the number of the palindromic substrings
	 */
	int countPalindromicSubstrings(string &str) {
		// write your code here
		int count=0;
		for(int i=0; i<str.length(); ++i){
			for(int j=i; j<str.length(); ++j){
				bool palindrome=true;
				for(int start=i, end=j; start<end && palindrome;)
					if(str[start++]!=str[end--]) palindrome=false;
				count += palindrome;
			}
		}
		return count;
	}
};

// Method 2, DP, Time O(n^2), Space O(n^2)
class Solution {
public:
	/**
	 * @param str: s string
	 * @return: return an integer, denote the number of the palindromic substrings
	 */
	int countPalindromicSubstrings(string &str) {
		// write your code here
		int count=0, n=str.length();
		vector<vector<bool> > dp(n,vector<bool>(n,false));
		for(int len=1; len<=n; ++len){
			for(int i=0; i+len<=n; ++i){
				int j=i+len-1;
				if(i+1<n && j-1>=0 && str[i]==str[j]) dp[i][j]=dp[i+1][j-1];
				if(str[i]==str[j] && abs(i-j)<2) dp[i][j]=true;
				count += dp[i][j];
			}
		}
		return count;
	}
};
